package main

import "fmt"

/*
给你一个整型数组，保证大小都为正，每个值代表直方图的高度，
求该图形能盛装几个格子的水

预处理数组 or 双指针
*/
func getMax(arr []int) int {
	N := len(arr)
	var sum int
	var LMax int = arr[0]
	var RMax []int = make([]int, N)  //预处理数组
	RMax[N-1] = arr[N-1]
	for i := N-2; i >= 0; i-- {
		RMax[i] = Max(RMax[i+1], arr[i])
	}

	for i := 1; i < N-1; i++ {
		min := Min(LMax, RMax[i+1])
		if arr[i] < min {
			sum += min - arr[i]
		} 
		if LMax < arr[i] {
			LMax = arr[i]
		}
	}
	return sum
}

//TODO 左右指针
func getMax2(arr []int) int {
	return 0
}

func main() {
	// arr := []int{3,1,2,5,2,4}
	arr := []int{4,5,1,3,2}
	fmt.Println(getMax(arr))
}

func Min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}